﻿/*
*	Sudoku game core logic.
*	All class are in "namespace" Sudoku. field and function names ended with "_" are private, DON'T use them.
*	
*	Sudoku.Board contains all core logic.
*	All the query methods are relatively fast, including get... check... etc.
*	The most expensive operation except Sudoku.Board.initialize are Sudoku.Board.setNumber, setNumberByLocation and setNumberByIndex,
*	because they maintain all the states of the game.
*	Sudoku.Board.initialize is very slow due to iteratively calling to Sudoku.Board.setNumberByPosition.
*	
*	@author: ylq
*	@date: 2012.06.27
*/


var Sudoku = {
};

/*
*	@return int: index of found element, -1 if not found.
*/
Sudoku.arrayFind = function (array, element) {
	var found = -1;
	for (var i = array.length - 1; i >= 0; --i) {
		if (array[i] == element) {
			found = i;
			break;
		}
	}
	return found;
};

/*
*	Remove element at index by move the last element to index then remove the last element.
*/
Sudoku.arraySwapBackRemove = function (array, index) {
	array[index] = array[array.length - 1];
	array.pop();
};

/*
*	Represent a position coordinate in the board. Upper left is (0, 0).
*	Use position.x and position.y to retrieve values.
*	Do not modify fields @x_ and @y_ after construct.
*/
Sudoku.Position = function (x, y) {
	this.x_ = x;
	this.y_ = y;
};

Object.defineProperty(Sudoku.Position.prototype, "x", {
	get: function () {
		return this.x_;
	}
});

Object.defineProperty(Sudoku.Position.prototype, "y", {
	get: function () {
		return this.y_;
	}
});

Sudoku.Position.prototype.toString = function () {
	return "(" + this.x_ + ", " + this.y_ + ")";
};

/*
*	@dimension int: board dimension. 4 * 4 board is dimension 2, 9 * 9 board is dimension 3, 16 * 16 board is dimension 4, etc.
*/
Sudoku.Board = function (dimension) {
	if (dimension < 2) {
		throw "dimension is invalid: " + dimension;
	}
	this.dimension_ = dimension;
	this.edgeLength_ = dimension * dimension;
	this.gridCount_ = this.edgeLength_ * this.edgeLength_;

	this.positionBuffer_ = new Array(this.gridCount_);
	for (var i = 0, currentX = 0, currentY = 0; i < this.gridCount_; ++i) {
		this.positionBuffer_[i] = new Sudoku.Position(currentX++, currentY);
		if (currentX == this.edgeLength_) {
			currentX = 0;
			currentY += 1;
		}
	}

	this.currentNumberCount_ = 0;

	this.numbers_ = new Array(this.gridCount_);
	for (var i = 0; i < this.gridCount_; ++i) {
		this.numbers_[i] = 0;
	}

	// this is the core thing
	// format: [(gridIndex, fixed size)[(number: from 1 to edgeLength, fixed size, 0 not used)[(influencing index)int]]]
	this.influencingIndices_ = new Array(this.gridCount_);
	for (var i = 0; i < this.gridCount_; ++i) {
		this.influencingIndices_[i] = new Array(this.edgeLength_ + 1);
		var influencingIndices = this.influencingIndices_[i];
		for (var j = 1; j < this.edgeLength_ + 1; ++j) {
			influencingIndices[j] = [];
		}
	}


	// a two dimension array, first dimension index is the number, second dimension contains grid positions have the same number.
	// first demension index 0 is not used.
	this.sameNumberPositions_ = new Array(this.edgeLength_ + 1);
	for (var i = 1; i < this.edgeLength_ + 1; ++i) {
		this.sameNumberPositions_[i] = [];
	}

	// all conflict position indices
	this.conflictPositions_ = [];

};

/*
*	@boardNumbers array<int>: 1 dimension array stores initial values. row major order.
*	@return array<Sudoku.Position>: array of conflict positions if have, empty array indicates valid.
*/
Sudoku.Board.prototype.initialize = function (boardNumbers) {
	if (boardNumbers.length != this.gridCount_) {
		throw "boardNumbers.length is not valid: " + boardNumbers + ", valid is: " + this.gridCount_;
	}

	for (var i = 0; i < this.gridCount_; ++i) {
		this.setNumberByPosition(this.getPositionFromIndex_(i), boardNumbers[i]);
	}

	return this.getAllConflictPositions();
};

Sudoku.Board.prototype.getEdgeLength = function () {
	return this.edgeLength_;
};

Sudoku.Board.prototype.getBoardGridCount = function () {
	return this.gridCount_;
};

/*
*	@return int: number
*/
Sudoku.Board.prototype.getNumber = function (x, y) {
	return this.numbers_[this.getIndexFromXY_(x, y)];
};

/*
*	@return int: number
*/
Sudoku.Board.prototype.getNumberByPosition = function (position) {
	return this.numbers_[this.getIndexFromPosition_(position)];
};

/*
*	@return int: number
*/
Sudoku.Board.prototype.getNumberByIndex = function (index) {
	return this.numbers_[index];
};

/*
*	@number int: 0 means remove number.
*	@return bool: true if game is finished.
*/
Sudoku.Board.prototype.setNumber = function (x, y, number) {
	return this.setNumberByPosition(this.getPositionFromXY_(x, y), number);
};

/*
*	@number int: 0 means remove number.
*	@return bool: true if game is finished.
*/
Sudoku.Board.prototype.setNumberByPosition = function (position, number) {
	if (number >= 0 && number <= this.edgeLength_) {
		var oldNumber = this.getNumberByPosition(position);
		if (oldNumber == number) {
			return this.isGameFinished();
		}

		var thisIndex = this.getIndexFromPosition_(position);

		this.setInfluencingIndicesByPosition_(position, oldNumber, false);

		this.setConflictIndices_(thisIndex, oldNumber, false);
		this.setConflictIndices_(thisIndex, number, true);

		this.setInfluencingIndicesByPosition_(position, number, true);

		this.setSameNumberPositions_(thisIndex, oldNumber, false);
		this.setSameNumberPositions_(thisIndex, number, true);

		// set a new number or remove an old number
		if (oldNumber === 0) {
			this.currentNumberCount_ += 1;
		}
		if (number === 0) {
			this.currentNumberCount_ -= 1;
		}

		this.numbers_[thisIndex] = number;
	} else {
		console.error("number is illegal. number: " + number);
	}
	return this.isGameFinished();
};

/*
*	@number int: 0 means remove number.
*	@return bool: true if game is finished.
*/
Sudoku.Board.prototype.setNumberByIndex = function (index, number) {
	return this.setNumberByPosition(this.getPositionFromIndex_(index), number);
};

/*
*	@number int: if number is 0, this will not work, simply return null.
*	@return array<Sudoku.Position>: postions, empty array indicates no same number in the board.
*/
Sudoku.Board.prototype.getSameNumberPostions = function (number) {
	if (number == 0 || number > this.edgeLength_) {
		return [];
	}

	var sameNumberPositions = this.sameNumberPositions_[number];
	return sameNumberPositions.map(function (element, i, array) {
		return this.getPositionFromIndex_(element);
	}, this);
};

/*
*	Use this method before filling the number to see conflicts if fill @number in.
*	@return array<Sudoku.Position>: conflict positions if have, empty array indicates valid.
*/
Sudoku.Board.prototype.checkValid = function (x, y, number) {
	return this.checkValidByIndex(this.getIndexFromXY_(x, y), number);
};

/*
*	Use this method before filling the number to see conflicts if fill @number in.
*	@return array<Sudoku.Position>: conflict positions if have, empty array indicates valid.
*/
Sudoku.Board.prototype.checkValidByPosition = function (position, number) {
	return this.checkValidByIndex(this.getIndexFromPosition_(position));
};

/*
*	Use this method before filling the number to see conflicts if fill @number in.
*	@return array<Sudoku.Position>: conflict positions if have, empty array indicates valid.
*/
Sudoku.Board.prototype.checkValidByIndex = function (index, number) {
	if (number == 0 || number > this.edgeLength_) {
		return [];
	}
	var influencingPositions = this.influencingIndices_[index][number];
	return influencingPositions.map(function (element, i, array) {
		return this.getPositionFromIndex_(element);
	}, this);
};

/*
*	Use this method after filling the number to see all conflicts with the number in this grid.
*	@return array<Sudoku.Position>: conflict positions if have, empty array indicates no conflict.
*/
Sudoku.Board.prototype.checkConflict = function (x, y) {
	return this.checkConflictByIndex(this.getIndexFromXY_(x, y));
};

/*
*	Use this method after filling the number to see all conflicts with the number in this grid.
*	@return array<Sudoku.Position>: conflict positions if have, empty array indicates no conflict.
*/
Sudoku.Board.prototype.checkConflictByPosition = function (position) {
	return this.checkConflictByIndex(this.getIndexFromPosition_(position));
};

/*
*	Use this method after filling the number to see all conflicts with the number in this grid.
*	@return array<Sudoku.Position>: conflict positions if have, empty array indicates no conflict.
*/
Sudoku.Board.prototype.checkConflictByIndex = function (index) {
	return this.checkValidByIndex(index, this.getNumberByIndex(index));
};

/*
*	@return array<bool>: indices corresponding to numbers, values is validness.
*/
Sudoku.Board.prototype.getValidNumbers = function (x, y) {
	return this.getValidNumbersByIndex(this.getIndexFromXY_(x, y));
};


/*
*	@return array<bool>: indices corresponding to numbers, values is validness.
*/
Sudoku.Board.prototype.getValidNumbersByPosition = function (position) {
	return this.getValidNumbersByIndex(this.getIndexFromPosition_(position));
};

/*
*	@return array<bool>: indices corresponding to numbers, values is validness.
*/
Sudoku.Board.prototype.getValidNumbersByIndex = function (index) {
	var arrayOfInfluencingIndices = this.influencingIndices_[index];
	return arrayOfInfluencingIndices.map(function (element, i, array) {
		return element.length == 0;
	}, this);
};

/*
*	@return array<Sudoku.Positon>
*/
Sudoku.Board.prototype.getAllConflictPositions = function () {
	return this.conflictPositions_.map(function (element, i, array) {
		return this.getPositionFromIndex_(element);
	}, this);
};

Sudoku.Board.prototype.getFilledGridCount = function () {
	return this.currentNumberCount_;
};

Sudoku.Board.prototype.isGameFinished = function () {
	if (this.currentNumberCount_ === this.gridCount_ && this.conflictPositions_.length === 0) {
		return true;
	}
	return false;
};

// Notice: almost copied from setOneNumberInfluencingIndices_
Sudoku.Board.prototype.setSameNumberPositions_ = function (thisIndex, number, isSet) {
	if (number == 0) {
		return;
	}
	var sameNumberPositions = this.sameNumberPositions_[number];
	var found = Sudoku.arrayFind(sameNumberPositions, thisIndex);

	if (found == -1) {
		if (isSet) {
			sameNumberPositions.push(thisIndex);
		} else {
			console.error("unsetting a same number position but not found: thisIndex: " + thisIndex + ", number: " + number);
		}
	} else {
		if (isSet) {
			console.error("setting a same number position that is already there: thisIndex: " + thisIndex + ", number: " + number);
		} else {
			Sudoku.arraySwapBackRemove(sameNumberPositions, found);
		}
	}

};

// Notice: code has been copied to setSameNumberPositions_
Sudoku.Board.prototype.setOneNumberInfluencingIndices_ = function (thisIndex, index, number, isSet) {
	if (thisIndex == index) {
		return;
	}
	var influencingIndices = this.influencingIndices_[index][number];
	var found = Sudoku.arrayFind(influencingIndices, thisIndex);

	if (found == -1) {
		if (isSet) {
			influencingIndices.push(thisIndex);
		} else {
			console.error("unsetting a valid number but not found: thisIndex: " + thisIndex + ", index: " + index + ", number: " + number);
		}
	} else {
		if (isSet) {
			console.error("setting a valid number that is already there: thisIndex: " + thisIndex + ", index: " + index + ", number: " + number);
		} else {
			Sudoku.arraySwapBackRemove(influencingIndices, found);
		}
	}
};

Sudoku.Board.prototype.setInfluencingIndicesByPosition_ = function (position, number, isSet) {
	if (number == 0) {
		return;
	}

	var blockX = Math.floor(position.x_ / this.dimension_);
	var blockY = Math.floor(position.y_ / this.dimension_);
	var thisIndex = this.getIndexFromPosition_(position);



	// horizontal
	var index = this.getIndexFromXY_(0, position.y_);
	var rowEndIndex = position.y_ * this.edgeLength_ + this.edgeLength_;
	for (; index < rowEndIndex; index += 1) {
		this.setOneNumberInfluencingIndices_(thisIndex, index, number, isSet);
	}

	// vertical
	var index = this.getIndexFromXY_(position.x_, 0);
	for (; index < this.gridCount_; index += this.edgeLength_) {
		this.setOneNumberInfluencingIndices_(thisIndex, index, number, isSet);
	}

	// block
	var index = this.getIndexFromXY_(blockX * this.dimension_, blockY * this.dimension_);
	for (var i = 0; i < this.dimension_; ++i) {
		for (var j = 0; j < this.dimension_; ++j) {
			if (!this.isInSameRowOrColumnByIndex_(thisIndex, index)) {
				this.setOneNumberInfluencingIndices_(thisIndex, index, number, isSet);
			}
			index += 1;
		}
		index += this.edgeLength_ - this.dimension_;
	}
};

// should be invoked after old value is unset if this is unset, or before new value is set if this set.
Sudoku.Board.prototype.setConflictIndices_ = function (index, number, isSet) {
	if (number == 0) {
		return;
	}
	// err... what the heck...

	// find all influencing grid positions about number about grid at index.
	// then check if they have already influenced by some other grids do nothing.
	// or they are not influenced by any grids, add the index of this grid to influencingIndices_.
	var conflictPositions = this.conflictPositions_;
	var influencingIndices = this.influencingIndices_[index][number];
	for (var i = influencingIndices.length - 1; i >= 0; --i) {
		var influencingIndex = influencingIndices[i];
		if (this.influencingIndices_[influencingIndex][number] == 0) {
			if (isSet) {
				conflictPositions.push(influencingIndex);
			} else {
				var found = Sudoku.arrayFind(conflictPositions, influencingIndex);
				Sudoku.arraySwapBackRemove(conflictPositions, found);
			}
		}
	}
	// if conflict happens, add grid at index itself into influencingIndices_.
	if (influencingIndices.length > 0) {
		if (isSet) {
			conflictPositions.push(index);
		} else {
			var found = Sudoku.arrayFind(conflictPositions, index);
			Sudoku.arraySwapBackRemove(conflictPositions, found);
		}
	}
};

Sudoku.Board.prototype.isInSameRowOrColumnByIndex_ = function (index1, index2) {
	var position1 = this.positionBuffer_[index1];
	var position2 = this.positionBuffer_[index2];
	return position1.x_ == position2.x_ || position1.y_ == position2.y_;
};

Sudoku.Board.prototype.getIndexFromPosition_ = function (position) {
	return position.x_ + position.y_ * this.edgeLength_;
};
Sudoku.Board.prototype.getIndexFromXY_ = function (x, y) {
	return x + y * this.edgeLength_;
};
Sudoku.Board.prototype.getPositionFromIndex_ = function (index) {
	return this.positionBuffer_[index];
};
Sudoku.Board.prototype.getPositionFromXY_ = function (x, y) {
	return this.positionBuffer_[x + y * this.edgeLength_];
};


/*
*	@return string: a string shows the board content that can be printed in the console.
*/
Sudoku.Board.prototype.getBroadString = function () {
	var result = "";
	for (var i = 0; i < this.edgeLength_; ++i) {
		for (var j = 0; j < this.edgeLength_; ++j) {
			result += "[" + this.numbers_[this.getIndexFromXY_(j, i)].toString(16) + "]\t";
		}
		result += "\n";
		var vnStartIndex = 1;
		for (var l = 0; l < this.dimension_; ++l) {
			for (var j = 0; j < this.edgeLength_; ++j) {
				var vnIndex = vnStartIndex;
				var validNumbers = this.getValidNumbers(j, i);
				for (var k = 0; k < this.dimension_; ++k) {
					result += (validNumbers[vnIndex] ? vnIndex.toString(16) : " ");
					vnIndex += 1;
				}
				result += "\t";
			}
			vnStartIndex += this.dimension_;
			result += "\n";
		}

		result += "\n";
	}
	return result;
};